package haxibiao

import "sort"

func twoSum(nums []int, target int) []int {
	// 双指针
	ano := make([]int, len(nums))
	copy(ano, nums)
	sort.Ints(ano)
	left, right := 0, len(nums)-1
	for left < right {
		sum := ano[left] + ano[right]
		if sum == target {
			break
		} else {
			if sum > target {
				right--
			} else {
				left++
			}
		}
	}
	ans := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		if nums[i] == ano[left] {
			ans = append(ans, i)
		}
	}
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] == ano[right] {
			ans = append(ans, i)
		}
	}
	return ans
}

func TwoSum2(nums []int, target int) []int {
	// 使用前一个target-cur，与后一个数进行对比
	hash := map[int]int{}
	for i, v := range nums {
		if j, ok := hash[target-v]; ok {
			return []int{j, i}
		}
		hash[v] = i
	}
	return nil
}
